//188 Best Time to Buy and Sell Stock IV
/*
给定一段时间内每天的股票价格，已知你只可以买卖各 k 次，且每次只能拥有一支股票，求
最大的收益

输入输出样例
	输入一个一维整数数组，表示每天的股票价格；以及一个整数，表示可以买卖的次数 k。输
出一个整数，表示最大的收益

Input: [3,2,6,5,0,3], k = 2
Output: 7
*/
// 主函数
int maxProfit(int k, vector<int> &prices)
{
	int days = prices.size();
	if (days < 2)
	{
		return 0;
	}
	if (k >= days)
	{
		return maxProfitUnlimited(prices);
	}
	vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0);
	for (int i = 0; i < days; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			buy[j] = max(buy[j], sell[j - 1] - prices[i]);
			sell[j] = max(sell[j], buy[j] + prices[i]);
		}
	}
	return sell[k];
}
// 辅函数
int maxProfitUnlimited(vector<int> prices)
{
	int maxProfit = 0;
	for (int i = 1; i < prices.size(); ++i)
	{
		if (prices[i] > prices[i - 1])
		{
			maxProfit += prices[i] - prices[i - 1];
		}
	}
	return maxProfit;
}
